package leetcode.array;


/**
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 *
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 *
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * @author MaoLin Wang
 * @date 2020/2/1718:33
 */
public class _04FindMedianSortedArrays {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length==0){
            return nums2.length%2==0?(double) (nums2[nums2.length/2-1]+nums2[nums2.length/2])/2:(double) nums2[nums2.length/2];
        }
        if (nums2.length==0){
            return nums1.length%2==0?(double)(nums1[nums1.length/2-1]+nums1[nums1.length/2])/2:(double)nums1[nums1.length/2];
        }
        int length=nums1.length+nums2.length;
        boolean oushu=length%2==0;
        int[] temp=new int[length/2+1];

        int i =0;
        int j =0;
        int count=0;
        while (count!=(length/2+1)) {
            if (i> (nums1.length-1)){
                temp[count]=nums2[j];
                j++;
                count++;
            }else if (j>(nums2.length-1)){
                temp[count]=nums1[i];
                i++;
                count++;
            }
            else if (nums1[i]<nums2[j]){
                temp[count]=nums1[i];
                count++;
                i++;
            }else{
                temp[count]=nums2[j];
                j++;
                count++;
            }
        }

        if (oushu){

            return (double) (temp[temp.length-1]+temp[temp.length-2])/2;
        }else {
            return (double) temp[temp.length-1];
        }
    }

    public static void main(String[] args) {
        int[] num1={100001};
        int [] num2={100000};
        double medianSortedArrays = findMedianSortedArrays(num1, num2);
        System.out.println(medianSortedArrays);
    }
}
